struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int x) : val(x), next(nullptr)
    {}
    ListNode(int x, ListNode * next) : val(x), next(next)
    {}
};

class Solution 
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        ListNode * _dummyHead = new ListNode(0, head);
        ListNode * slow = _dummyHead;
        ListNode * fast = _dummyHead;
        for(int i = 0; i < n; i++)
        {
            fast = fast->next;
        }
        while (fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return _dummyHead->next;
    }
};

#include <iostream>
#include <vector>

// 辅助函数：根据数组创建链表
ListNode* createList(const std::vector<int>& vals) {
    if (vals.empty()) return nullptr;
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    for (int v : vals) {
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur) {
        std::cout << cur->val;
        if (cur->next) std::cout << "->";
        cur = cur->next;
    }
    std::cout << std::endl;
}

int main() {
    Solution sol;

    // 测试用例1：删除倒数第2个节点
    std::vector<int> vals1 = {1, 2, 3, 4, 5};
    ListNode* head1 = createList(vals1);
    std::cout << "原链表1: ";
    printList(head1);
    ListNode* result1 = sol.removeNthFromEnd(head1, 2);
    std::cout << "删除倒数第2个节点后: ";
    printList(result1);
    std::cout << std::endl;

    // 测试用例2：删除唯一节点
    std::vector<int> vals2 = {1};
    ListNode* head2 = createList(vals2);
    std::cout << "原链表2: ";
    printList(head2);
    ListNode* result2 = sol.removeNthFromEnd(head2, 1);
    std::cout << "删除倒数第1个节点后: ";
    if (result2 == nullptr) {
        std::cout << "空链表" << std::endl;
    } else {
        printList(result2);
    }
    std::cout << std::endl;

    // 测试用例3：删除第一个节点（倒数第n个）
    std::vector<int> vals3 = {1, 2};
    ListNode* head3 = createList(vals3);
    std::cout << "原链表3: ";
    printList(head3);
    ListNode* result3 = sol.removeNthFromEnd(head3, 2);
    std::cout << "删除倒数第2个节点后: ";
    printList(result3);
    std::cout << std::endl;

    // 测试用例4：删除最后一个节点
    std::vector<int> vals4 = {1, 2, 3};
    ListNode* head4 = createList(vals4);
    std::cout << "原链表4: ";
    printList(head4);
    ListNode* result4 = sol.removeNthFromEnd(head4, 1);
    std::cout << "删除倒数第1个节点后: ";
    printList(result4);

    return 0;
}
